package LeetCode_572;



/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/26 21:52
 * 572. 另一棵树的子树
 * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
 *
 * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
 *
 * 思路： 拆解为：1.查找节点
 *              2.判断相同树
 */
public class Solution1 {
    public static void main(String[] args) {
        TreeNode left = new TreeNode(1);
        TreeNode root = new TreeNode(1);
        root.left = left;
        TreeNode subRoot = new TreeNode(1);
        Solution1 solution= new Solution1();
        boolean b = solution.isSubtree(root,subRoot);
        System.out.println(b);
    }
    private boolean dfs (TreeNode root, TreeNode targetNode){
        if (root == null){
            return false;
        }
        return check(root,targetNode)
                || dfs(root.left,targetNode)
                || dfs(root.right,targetNode);
    }
    private boolean check(TreeNode root, TreeNode subRoot){
        if (root ==null &&subRoot==null){
            return true;
        }
        if (root == null || subRoot == null ||root.val != subRoot.val){
            return false;
        }
        return check(root.left,subRoot.left) && check(root.right,subRoot.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root,subRoot);
    }

}
